# 第2节再谈最小生成树
# prim算法
if __name__ == '__main__':
    n, m = 6, 9
    a = [[2, 4, 11], [3, 5, 13], [4, 6, 3], [5, 6, 4], [2, 3, 6], [4, 5, 7], [1, 2, 1], [3, 4, 9], [1, 3, 2]]
    inf = 999
    # 二维数组存储图
    e = [[0 for i in range(0, 8)] for i in range(0, 8)]
    print(e)
    # 初始化
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = inf

    # a = [[2, 4, 11], [3, 5, 13], [4, 6, 3], [5, 6, 4], [2, 3, 6], [4, 5, 7], [1, 2, 1], [3, 4, 9], [1, 3, 2]]
    # 读入边
    for i, v in enumerate(a):
        e[v[0]][v[1]] = v[2]
        e[v[1]][v[0]] = v[2]

    print(e)

    # 初始化dis数组，这里是1号顶点到各个顶点的初始距离，因为当前生成树中只有1号顶点
    dis = [0 for i in range(0, n + 1)]
    book = [0 for i in range(0, n + 1)]
    for i, v in enumerate(dis):
        dis[i] = e[1][i]

    print(dis)

    # prim 核心算法
    book[1] = 1
    count, j, s = 0, 0, 0
    count += 1
    while count < n:
        min_ = inf
        for i in range(1, n + 1):
            if book[i] == 0 and dis[i] < min_:
                min_ = dis[i]
                j = i
        book[j] = 1
        count += 1
        s += dis[j]

        # 扫播当前顶点j所有的边，再以j为中间点，更新生成树到每一个非树顶点的距离
        # 也就是说现在记录的最短距离，不是每个顶点到﹖号顶点的最短距离，而是每个顶一个“树顶点"已被选入生成树的顶点)的最短距离,
        # 即如果dis[k]>e[][k]( 1<k<=n)lis[k]=e[][k]。因此在计算更新最短路径的时候不再需要加上dis[门]了，
        # 因为我们的目非得靠近1号顶点，而是靠近“生成树”就可以。也就是说只需要靠近“生成树”任意-个“树顶点”就行。
        # 找1号顶点的最近点的时候，1号顶点的最近点已经找到，接下来找2号顶点的最近点即可
        for k in range(1, n + 1):
            if book[k] == 0 and dis[k] > e[j][k]:
                dis[k] = e[j][k]

    print('%d' % s)
